package leetcode.dfs;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

//797. 所有可能的路径
public class AllPathsSourceTarget {

    //DFS+回溯

    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> stack = new ArrayList<>();

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        stack.add(0);
        dfs(graph, 0, graph.length - 1);
        return ans;
    }

    private void dfs(int[][] graph, int i, int n) {
        if (i == n) {
            ans.add(new ArrayList<Integer>(stack));
            return;
        }
        for (int y : graph[i]) {
            stack.add(y);
            dfs(graph, y, n);
            //回溯
            stack.remove(stack.size() - 1);
        }
    }


}
